package com.atguigu.mapreduce.Algorithm;

/**
 * @author laberinto
 * @version 1.0
 * @date 2024/10/22 16:38
 * @package com.atguigu.mapreduce.Algorithm
 * @message \\桶排序
 * (⌓‿⌓)
 */
import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
    public static void bucketSort(int[] arr) {
        if (arr.length == 0){
            return;
        }

        // 创建桶
        int numOfBuckets = 10;
        ArrayList<Integer>[] buckets = new ArrayList[numOfBuckets];

        for (int i = 0; i < numOfBuckets; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素分配到桶中
        for (int num : arr) {
            int bucketIndex = (int) (num * numOfBuckets); // 根据数值确定桶的索引
            if (bucketIndex >= numOfBuckets) {
                bucketIndex = numOfBuckets - 1; // 边界条件处理
            }
            buckets[bucketIndex].add(num);
        }

        // 对每个桶进行排序并合并
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket); // 使用 Collections.sort() 对桶内元素进行排序
            for (int num : bucket) {
                arr[index++] = num; // 合并
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {9,2,5,3,1,4,8,0,7,6};
        System.out.println("原始数组: ");
        for (float num : arr) {
            System.out.print(num + " ");
        }

        bucketSort(arr);

        System.out.println("\n排序后数组: ");
        for (float num : arr) {
            System.out.print(num + " ");
        }
    }
}